//
// Description: 5941. 找出知晓秘密的所有专家
// Created by Loading on 2021/11/28.
//

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e5 + 10; // 数据量
int father[N];     // 集 （父节点集合）

// 初始化
void Init(int n) {
    // 在合并之前初始化每个节点为该集合的根节点（每个数都是一个集合，自己的父节点初始化为自己）
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

// 查
int FindFather(int x) {
    /* 功能：找到元素x在该集合中的根节点（根节点满足x == father[x]） */

    // 记录初始节点
    int a = x;
    // 循环查找父节点，找到集合的根节点
    while (x != father[x]) {
        x = father[x];   // 循环结束后的 x 为该集合的根节点
    }
    /* 路径压缩，将寻找根节点路途中的每个节点指向其根节点，优化之后的查找速度，可不写 */
    while (a != father[a]) {
        int b = a;      // 记录 a，防止后面被覆盖
        a = father[a];  // 让 a 指向其父节点
        father[b] = x;  // 指向根节点
    }
    return x;
}

// 并
void Union(int a, int b) {
    /* 功能：将 a 与 b 合并到一个集合中 */

    // 分别找到 a, b 所在结合的根节点
    int Ra = FindFather(a);
    int Rb = FindFather(b);
    // 当 a, b 不在同一个集合中时将 Ra 指向 Rb，或者将 Rb 指向 Ra （选择一个作为根节点）
    if (Ra != Rb) {
        // 将 Ra 指向 Rb
        father[Ra] = Rb;
        // father[Rb] = Ra; 也可以
    }
}

/* 并查集 */
vector<int> findAllPeople(int n, vector<vector<int>> &meetings, int firstPerson) {
    Init(n);
    // 第一个知晓秘密的人父节点指向 0
    father[firstPerson] = 0;
    // 是否知晓秘密标识数组
    vector<bool> know(n, false);
    know[0] = know[firstPerson] = true;
    // 按照会议时间排序
    sort(meetings.begin(), meetings.end(), [](auto &v1, auto &v2) {
        return v1[2] < v2[2];
    });

    int meet_size = meetings.size();
    for (int i = 0; i < meet_size; ++i) {
        // index 为时间相同的会议的索引 + 1，[i，index - 1] 之间为时间相同的会议
        int index = i + 1;
        while (index < meet_size && meetings[i][2] == meetings[index][2]) {
            ++index;
        }
        // 聚合
        for (int j = i; j < index; ++j) {
            Union(meetings[j][0], meetings[j][1]);
        }
        // 查找每个专家的父节点是否和 0 的父节点一致
        for (int j = i; j < index; ++j) {
            if (FindFather(meetings[j][0]) == FindFather(0)) {
                // 与 0 的父节点一致，标识知晓秘密，更新 know 数组
                know[meetings[j][0]] = true;
                know[meetings[j][1]] = true;
            } else {
                /* 不一致时，代表不知晓秘密，要解除聚合，否则影响后续计算 */
                father[meetings[j][0]] = meetings[j][0];
                father[meetings[j][1]] = meetings[j][1];
            }
        }
        // 移动 i
        i = index - 1;
    }

    vector<int> res;
    for (int i = 0; i < n; ++i) {
        if (know[i]) {
            res.emplace_back(i);
        }
    }

    return res;
}

int main() {
    int n = 6;
    vector<vector<int>> meetings = {{1, 2, 5},
                                    {2, 3, 8},
                                    {1, 5, 10}};
    int firstPerson = 1;
    vector<int> res = findAllPeople(n, meetings, firstPerson);
    for (auto &x : res) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}